public class Solution1071 {
    public String gcdOfStrings(String str1, String str2) {
        for (int i=Math.min(str1.length(),str2.length());i>0;i--){
            if (str1.length()%i==0 && str2.length()%i==0){
                String a=str1.substring(0,i);
                String b=str2.substring(0,i);
                if (a.equals(b)){
                    StringBuilder s1=new StringBuilder();
                    for (int j=0;j<str1.length()/i;j++){
                        s1.append(a);
                    }
                    StringBuilder s2=new StringBuilder();
                    for (int j=0;j<str2.length()/i;j++){
                        s2.append(a);
                    }
                    if (s1.toString().equals(str1) && s2.toString().equals(str2)){
                        return a;
                    }
                }
            }
        }
        return "";
    }

    public static void main(String[] args) {
        System.out.println(new Solution1071().gcdOfStrings("ABABAB","ABAB"));
    }
}
